SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Hashed array tree</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Hashed array tree</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>hashed array tree</b> (<b>HAT</b>) is a <a href="Dynamic_array" title="Dynamic array">dynamic array</a> data-structure published by Edward Sitarski in 1996,<sup id="cite_ref-sitarski96_1-0" class="reference"><a href="#cite_note-sitarski96-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> maintaining an array of separate memory fragments (or "leaves") to store the data elements, unlike simple dynamic arrays which maintain their data in one contiguous memory area. Its primary objective is to reduce the amount of element copying due to automatic array resizing operations, and to improve memory usage patterns.

</p><p>Whereas simple dynamic arrays based on <a href="Dynamic_array#Geometric_expansion_and_amortized_cost" title="Dynamic array">geometric expansion</a> waste linear (Ω(<i>n</i>)) space, where <i>n</i> is the number of elements in the <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a>, hashed array trees waste only order <i>O</i>(<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span>) storage space. An optimization of the algorithm allows elimination of data copying completely, at a cost of increasing the wasted space.

</p><p>It can perform <a href="Random_access" title="Random access">access</a> in constant (<a href="Big_O_notation" title="Big O notation">O</a>(1)) time, though slightly slower than simple dynamic arrays. The algorithm has O(1) amortized performance when appending a series of objects to the end of a hashed array tree. Contrary to its name, it does not use <a href="Hash_function" title="Hash function">hash functions</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<p>As defined by Sitarski, a hashed array tree has a top-level directory containing a <a href="Power_of_two" title="Power of two">power of two</a> number of leaf arrays. All leaf arrays are the same size as the top-level directory. This structure superficially resembles a <a href="Hash_table" title="Hash table">hash table</a> with array-based collision chains, which is the basis for the name <i>hashed array tree</i>. A full hashed array tree can hold <i>m</i><sup>2</sup> elements, where <i>m</i> is the size of the top-level directory.<sup id="cite_ref-sitarski96_1-1" class="reference"><a href="#cite_note-sitarski96-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The use of powers of two enables faster physical addressing through bit operations instead of arithmetic operations of <a href="Quotient" title="Quotient">quotient</a> and <a href="Remainder" title="Remainder">remainder</a><sup id="cite_ref-sitarski96_1-2" class="reference"><a href="#cite_note-sitarski96-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and ensures the O(1) amortized performance of append operation in the presence of occasional global array copy while expanding.

</p>

<div class="mw-heading mw-heading2"><h2 id="Expansions_and_size_reductions">Expansions and size reductions</h2></div>

<p>In a usual dynamic array <a href="Dynamic_array#Geometric_expansion_and_amortized_cost" title="Dynamic array">geometric expansion</a> scheme, the array is reallocated as a whole sequential chunk of memory with the new size a double of its current size (and the whole data is then moved to the new location). This ensures O(1) amortized operations at a cost of O(n) wasted space, as the enlarged array is filled to the half of its new capacity.

</p><p>When a hashed array tree is full, its directory and leaves must be restructured to twice their prior size to accommodate additional append operations. The data held in old structure is then moved into the new locations. Only one new leaf is then allocated and added into the top array which thus becomes filled only to a quarter of its new capacity. All the extra leaves are not allocated yet, and will only be allocated when needed, thus wasting only <i>O</i>(<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>n</i></span></span>) of storage.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>There are multiple alternatives for reducing size: when a hashed array tree is one eighth full, it can be restructured to a smaller, half-full hashed array tree; another option is only freeing unused leaf arrays, without resizing the leaves. Further optimizations include adding new leaves without resizing while growing the directory array as needed, possibly through geometric expansion. This will eliminate the need for data copying completely at the cost of making the wasted space be <i>O</i>(<i>n</i>), with a small constant, and only performing restructuring when a set threshold overhead is reached.<sup id="cite_ref-sitarski96_1-3" class="reference"><a href="#cite_note-sitarski96-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_data_structures">Related data structures</h2></div>

<caption>Comparison of list data structures

</caption>

</th>

<th rowspan="2">Peek <br>(index)

</th>

<th colspan="3">Mutate (insert or delete) at …

</th>

<th rowspan="2">Excess space, <br>average

</th></tr>

<tr>

<th>Beginning

</th>

<th>End

</th>

<th>Middle

</th></tr>

<tr>

<td><a href="Linked_list" title="Linked list">Linked list</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1), known end element;<br>Θ(<i>n</i>), unknown end element

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td></tr>

<tr>

<td><a href="Array_data_structure" class="mw-redirect" title="Array data structure">Array</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td data-sort-value="" style="background: var(--background-color-interactive, #ececec); color: var(--color-base, inherit); vertical-align: middle; text-align: center;" class="table-na">—

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">0

</td></tr>

<tr>

<td><a href="Dynamic_array" title="Dynamic array">Dynamic array</a>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1) <a href="Amortized_analysis" title="Amortized analysis">amortized</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

</td></tr>

<tr>

<td><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Balanced tree</a>

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log n)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log <i>n</i>)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(log <i>n</i>)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td></tr>

<tr>

<td>Random-<span class="nowrap">access list</span>

</td>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

</td>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td></tr>

<tr>

<td>

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1)

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Θ(1) <a href="Amortized_analysis" title="Amortized analysis">amortized</a>

</td>

<td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">Θ(<i>n</i>)

</td>

<td style="background:#FFB; color:black;vertical-align:middle;text-align:center;" class="table-partial">Θ(√<i>n</i>)

</td></tr></tbody></table>

<p><br>

Brodnik et al.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> presented a <a href="Dynamic_array" title="Dynamic array">dynamic array</a> algorithm with a similar space wastage profile to hashed array trees. Brodnik's implementation retains previously allocated leaf arrays, with a more complicated address calculation function as compared to hashed array trees.

</p>

<ul><li><a href="Dynamic_array" title="Dynamic array">Dynamic array</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSitarski1996" class="citation magazine cs1">Sitarski, Edward (September 1996). <a rel="nofollow" class="external text" href="http://www.ddj.com/architect/184409965?pgno=5">"Algorithm Alley -- HATs: Hashed array trees"</a>. <i>Dr. Dobb's Journal</i>. Vol. 21, no. 11.</cite></span>

</li>

<cite id="CITEREFKatajainen2016" class="citation conference cs1">Katajainen, Jyrki (June 5–8, 2016). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://books.google.com/books?id=NY1FDAAAQBAJ">"Worst-Case-Efficient Dynamic Arrays in Practice"</a></span>. In Kulikov, Alexander S.; Goldberg, Andrew V. (eds.). <i>Experimental Algorithms</i>. 15th International Symposium on Experimental Algorithms, SEA 2016. Lecture Notes in Computer Science. Vol. 9685. <a href="Saint_Petersburg" title="Saint Petersburg">St. Petersburg, Russia</a>: <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer Science+Business Media</a>. p. 173. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-38851-9_12">10.1007/978-3-319-38851-9_12</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-38851-9</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFBrodnikCarlssonSedgewickMunro1999" class="citation cs2">Brodnik, Andrej; Carlsson, Svante; <a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Munro, JI; Demaine, ED (1999), <a rel="nofollow" class="external text" href="http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf"><i>Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09)</i></a> <span class="cs1-format">(PDF)</span>, Department of Computer Science, University of Waterloo</cite></span>

</li>

<li id="cite_note-okasakiComparison-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-okasakiComparison_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-okasakiComparison_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-okasakiComparison_4-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFChris_Okasaki1995" class="citation journal cs1">Chris Okasaki (1995). "Purely Functional Random-Access Lists". <i>Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture</i>: <span class="nowrap">86–</span>95. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F224164.224187">10.1145/224164.224187</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFBrodnikCarlssonSedgewickMunro1999" class="citation cs2">Brodnik, Andrej; Carlsson, Svante; <a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Munro, JI; Demaine, ED (1999), <a rel="nofollow" class="external text" href="http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf">"Resizable Arrays in Optimal Time and Space"</a> <span class="cs1-format">(PDF)</span>, <i>Technical Report CS-99-09</i>, Department of Computer Science, University of Waterloo</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Associative_array" title="Associative array">Associative array</a>

<ul><li><a href="Multimap" title="Multimap">Multimap</a></li>

<li><a href="Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a>

<ul><li><a href="Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li>

<li><a href="Priority_queue" title="Priority queue">Priority queue</a>

<ul><li><a href="Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li>

<ul><li><a href="Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li>

<li><a href="Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bit_array" title="Bit array">Bit array</a></li>

<li><a href="Circular_buffer" title="Circular buffer">Circular buffer</a></li>

<li><a href="Dynamic_array" title="Dynamic array">Dynamic array</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Association_list" title="Association list">Association list</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li>

<li><a href="XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li></ul></li>

<ul><li><a href="Binary_heap" title="Binary heap">Binary heap</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial heap</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li>

<li><a href="Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-25" href="https://en.wikipedia.org/wiki/?title=Hashed_array_tree&oldid=1292070460">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>